
namespace AlgorithmQuickSort {
    // show debug log
    const isDebug: boolean = true;

    // 快速排序
    function quickSort(ary: number[], left?: number, right?: number) {
        const len = ary.length;
        left = typeof left == 'number' ? left : 0;
        right = typeof right == 'number' ? right : (len - 1);

        if (left < right) {
            const partitionIndex = partition(ary, left, right);
            quickSort(ary, left, partitionIndex - 1);
            quickSort(ary, partitionIndex + 1, right);
        }
        return ary;
    }
    // 分区操作
    function partition(ary: number[], left: number, right: number) {
        // 设定基准值（pivot）
        const pivot = left;
        if (isDebug)
            console.log(`开始分区操作[${left},${right}]，设定基准值${pivot}，排序前数组：\n`, JSON.stringify(ary.slice(left, right + 1)), "\n");
        let index = pivot + 1;
        for (var i = index; i <= right; i++) {
            if (ary[i] < ary[pivot]) {
                swap(ary, i, index);
                index++;
            }
        }
        swap(ary, pivot, index - 1);
        if (isDebug)
            console.log(`分区[${left},${right}]遍历结束，分区返回pos=${index - 1}, 此刻数组:\n`, JSON.stringify(ary.slice(left, right + 1)), "\n");
        return index - 1;
    }
    // 数组内数据交换
    function swap(ary: number[], i: number, j: number) {
        if (i == j) return;
        const temp = ary[i];
        ary[i] = ary[j];
        ary[j] = temp;
        if (isDebug)
            console.log(`数组${i}与${j}交换，交换后数组：\n`, JSON.stringify(ary), "\n");
    }

    function main() {
        const ary: number[] = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
        if (isDebug)
            console.log(`数组长度${ary.length}，排序前数组：\n`, JSON.stringify(ary), "\n");
        quickSort(ary);
        if (isDebug)
            console.log(`排序后数组：\n`, JSON.stringify(ary), "\n");
    }
    main();
}